package com.ma.sort;

import java.util.PriorityQueue;

import static com.ma.tool.system.basics.swap;

/**
 * 额外空间复杂度O(1)
 */
public class heapSort {

    /**
     * 堆排序
     * O(N*logN)
     * @param arr
     */
    public static void run(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        /**
         * 使这个数组变成大根堆
         */
        //O(N*logN)
        for(int i=0;i<arr.length;i++){//O(N)
            heapInsert(arr,i);//O(logN)
        }
/*        //O(N)
        //等比数列
        for(int i=arr.length-1;i>=0;i--){
            heapify(arr,i,arr.length);
        }*/
        int heapSize=arr.length;
        /**
         * 将最后一个元素与第一个交换(第一个始终是最大的那个)，将最大的扔到最后然后不管它逐渐缩小范围
         *
         * 4231->123 4->321 4->12  34->21 34->1 234->1234
         */
        swap(arr,0,--heapSize);
        /**
         * 不看最后一项 使其它也是一个大根堆
         */
        while (heapSize>0){//O(N*logN)
            //前面swap换好的到第一个位置的值下沉（此时已经没有最大值的事儿了，他已经在后面了只需要管剩下的最大值仍在他前面）
            heapify(arr,0,heapSize);
            //交换当前大根堆的头和尾,重复上面操作,直到向前缩小到只有一个才停止
            swap(arr,0,--heapSize);
        }
    }


    /**
     * 大根堆下沉操作
     * @param arr
     * @param index
     * @param heapSize
     */
    private static void heapify(int[] arr,int index,int heapSize){
        int left=index*2+1;//左孩子
        while (left<heapSize){
            //判断啊当前（index）节点的子节点相互比较，左节点一定存在，判断右节点是否存在且大于左节点
            int largest=(left+1)<heapSize&&arr[left + 1]>arr[left]?left+1:left;
            //判断最大的子节点是否比父节点（index）大，把大的记录下来
            largest=arr[largest]>arr[index]?largest:index;

            //如果子节点都小于父节点，则不需要下沉
            if(largest==index){
                break;
            }
            //交换大子节点与父节点
            swap(arr, index, largest);
            //变换父节点，继续循环，继续看是否需要继续下沉
            index=largest;
            left=index*2+1;

        }
    }
    /**
     * 大根堆添加操作
     * @param arr
     * @param index
     */
    private static void heapInsert(int[] arr,int index){
        //只有arr[index]大于父节点时才上升，父节点下沉
        while (arr[index]>arr[((index-1)>>1)<0?0:(index-1)>>1]){
            swap(arr,index,(index-1)>>1);
            index=((index-1)>>1)<0?0:(index-1)>>1;
        }
    }


    /**
     * 用小根堆实现部分有序 O(N*logK)
     * @param arr
     * @param k
     */
    public static void partiallyOrdered(int[] arr,int k){
        PriorityQueue<Integer> heap=new PriorityQueue<>();
        int index=0;
        for(;index<=Math.min(arr.length-1,k);index++){
            //将前k个加入到小根堆
            heap.add(arr[index]);
        }
        int i=0;
        for(;index<arr.length;i++,index++){
            //从k+1位置开始先将k+1压入小根堆,再弹出小根堆头部即最小的
            heap.add(arr[index]);
            arr[i]=heap.poll();

        }
        while(!heap.isEmpty()){
            //将剩下没弹出来的加arr里
            arr[i++]=heap.poll();
        }
    }



}
